﻿// 版权 ©2015-2018 SoftWx, Inc.
// 根据 MIT 许可证发布，许可证文本位于文件末尾。
// 作者: Steve Hatchett

using System;
using System.Runtime.CompilerServices;

namespace PhraseCorrector.SpellCore
{
    /// <summary>
    /// 提供优化方法以计算两个字符串之间的 Damerau-Levenshtein 最优字符串对齐（OSA）比较的类。
    /// </summary>
    /// <remarks>
    /// 版权 ©2015-2018 SoftWx, Inc.
    ///
    /// 创建高度优化的编辑距离函数的灵感来自 Sten Hjelmqvist 的“快速、内存高效”算法，该算法描述在
    /// http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm
    ///
    /// Damerau-Levenshtein 算法基本上是 Levenshtein 算法的一个变种，它将相邻字符的交换视为单一编辑操作。
    /// 详细的优化算法在我的博客文章中有详细描述：
    /// http://blog.softwx.net/2015/01/optimizing-damerau-levenshtein_15.html
    ///
    /// 参见 http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
    ///
    /// 注意，这个实现的 Damerau-Levenshtein 是更简单且更快的最优字符串对齐（也称为受限编辑）距离，
    /// 它与经典的算法略有不同，因为它限制了任何子串只能被编辑一次。例如，“CA”到“ABC”的编辑距离
    /// 在完全应用 Damerau-Levenshtein 算法时为 2，但在本类实现的方法中为 3（使用最优字符串对齐算法）。
    /// 这意味着该算法不是一个真正的度量，因为它不满足三角不等式。然而，在实际应用中，这种 OSA 版本可能是所需的。
    /// 除了更快之外，它不会给长距离的交换分配较低的距离分数。实际上，人类错误的交换最可能发生在相邻字符之间。
    /// 例如，经典的 Damerau 算法给这两个字符串：“sated”和“dates”分配一个距离为 1（将 's' 和 'd' 视为一次交换）。
    /// 本类中的 Damerau 最优字符串对齐版本给这两个字符串分配一个距离为 2（两次替换），因为它只计算相邻字符的交换。
    ///
    /// 本类中的方法不是线程安全的。如果需要线程安全，请使用 Distance 类中的静态方法。
    /// </remarks>
    public class DamerauOSA : IDistance {

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////      
        /// <summary>
        /// 存储基础成本的数组，用于计算Damerau-Osa编辑距离。
        /// </summary>
        private int[] baseChar1Costs;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 存储前一个字符的成本数组，用于优化Damerau-Osa编辑距离计算。
        /// </summary>
        private int[] basePrevChar1Costs;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 创建一个新的DamerauOSA实例，默认初始化成本数组为空数组。
        /// </summary>
        public DamerauOSA()
        {
            SetCoastSize(0);
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 使用指定的最大字符串长度创建一个新的DamerauOSA实例。
        /// 通过指定最大预期字符串长度，可以提高内存效率。
        /// </summary>
        /// <param name="expectedMaxStringLength">
        /// 预期的最大字符串长度，用于初始化成本数组的大小。
        /// </param>
        public void SetCoastSize(int expectedMaxStringLength) {
            this.baseChar1Costs= new int[expectedMaxStringLength];
            this.basePrevChar1Costs= new int[expectedMaxStringLength];
        }
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////       
        /// <summary>
        /// 计算并返回两个字符串之间的Damerau-Levenshtein最优字符串对齐编辑距离。
        /// </summary>
        /// <remarks>
        /// 参考链接: https://github.com/softwx/SoftWx.Match
        /// 此方法不是线程安全的。
        /// </remarks>
        /// <param name="string1">要比较的第一个字符串。</param>
        /// <param name="string2">要比较的另一个字符串。</param>
        /// <returns>
        /// 如果字符串相同则返回0，否则返回一个正数，数值大小随字符串差异增加而增大。
        /// </returns>
        public double Distance(string string1, string string2)
        {
            if (string1== null) return (string2 ?? "").Length;
            if (string2== null) return string1.Length;

            // 如果字符串长度不同，确保较短的字符串是string1。这样可以在主处理过程中更多地在内循环中旋转，从而加快速度。
            if (string1.Length > string2.Length) { var t= string1; string1= string2; string2= t; }

            // 识别可以忽略的公共前后缀
            Helpers.PrefixSuffixPrep(string1, string2, out int len1, out int len2, out int start);
            if (len1== 0) return len2;

            if (len2 > this.baseChar1Costs.Length) SetCoastSize(len2);

            return Distance(string1, string2, len1, len2, start, this.baseChar1Costs, this.basePrevChar1Costs);
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////     
        /// <summary>
        /// 计算并返回两个字符串之间的Damerau-Levenshtein最优字符串对齐编辑距离。
        /// </summary>
        /// <remarks>
        /// 参考链接: https://github.com/softwx/SoftWx.Match
        /// 此方法不是线程安全的。
        /// </remarks>
        /// <param name="string1">要比较的第一个字符串。</param>
        /// <param name="string2">要比较的另一个字符串。</param>
        /// <param name="maxDistance">感兴趣的最远距离阈值。</param>
        /// <returns>
        /// 如果距离大于最大距离阈值则返回-1；如果字符串相同则返回0；否则返回一个正数，数值大小随字符串差异增加而增大。
        /// </returns>
        public double Distance(string string1, string string2, double maxDistance)
        {
            if (string1== null || string2== null) return Helpers.NullDistanceResults(string1, string2, maxDistance);
            if (maxDistance <= 0) return (string1== string2) ? 0 : -1;
            maxDistance= Math.Ceiling(maxDistance);
            int iMaxDistance= (maxDistance <= int.MaxValue) ? (int)maxDistance : int.MaxValue;

            // 如果字符串长度不同，确保较短的字符串是string1。这样可以在主处理过程中更多地在内循环中旋转，从而加快速度。
            if (string1.Length > string2.Length) { string t= string1; string1= string2; string2= t; }
            if (string2.Length - string1.Length > iMaxDistance) return -1;

            // 识别可以忽略的公共前后缀
            Helpers.PrefixSuffixPrep(string1, string2, out int len1, out int len2, out int start);
            if (len1== 0) return (len2 <= iMaxDistance) ? len2 : -1;

            if (len2 > this.baseChar1Costs.Length)
            {
                this.baseChar1Costs= new int[len2];
                this.basePrevChar1Costs= new int[len2];
            }
            if (iMaxDistance < len2)
                return Distance(string1, string2, len1, len2, start, iMaxDistance, this.baseChar1Costs, this.basePrevChar1Costs);

            return Distance(string1, string2, len1, len2, start, this.baseChar1Costs, this.basePrevChar1Costs);
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// Damerau-Levenshtein最优字符串对齐算法的核心内部实现。
        /// </summary>
        /// <remarks>参考链接: https://github.com/softwx/SoftWx.Match</remarks>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int Distance(string string1, string string2, int len1, int len2, int start, int[] char1Costs, int[] prevChar1Costs)
        {
                int leftCharCost, aboveCharCost;
            for (int j= 0; j < len2;) char1Costs[j]= ++j;

            char char1= ' ';
            int currentCost= 0;
            for (int i= 0; i < len1; ++i)
            {
                char prevChar1= char1;
                char1= string1[start + i];

                char char2= ' ';
                leftCharCost= aboveCharCost= i;
                int nextTransCost= 0;

                for (int j= 0; j < len2; ++j)
                {
                    int thisTransCost= nextTransCost;
                    nextTransCost= prevChar1Costs[j];
                    prevChar1Costs[j]= currentCost= leftCharCost; // 对角线成本（替换）
                    leftCharCost= char1Costs[j];    // 左边现在等于当前成本（下一次迭代时将是对角线）

                    char prevChar2= char2;
                    char2= string2[start + j];

                    if (char1 != char2)
                    {
                        // 如果不满足以下两个条件，则进行替换
                        if (aboveCharCost < currentCost) currentCost= aboveCharCost; // 删除
                        if (leftCharCost < currentCost) currentCost= leftCharCost;   // 插入

                        ++currentCost;

                        if ((i != 0) && (j != 0) && (char1== prevChar2)   && (prevChar1== char2) && (thisTransCost + 1 < currentCost))
                            currentCost= thisTransCost + 1; // 转换
                    }

                    char1Costs[j]= aboveCharCost= currentCost;
                }
            }

            return currentCost;
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// Damerau-Levenshtein 最优字符串对齐算法的核心内部实现，接受最大距离限制。
        /// </summary>
        /// <remarks>参考链接: https://github.com/softwx/SoftWx.Match</remarks>
        internal static int Distance(string string1, string string2, int len1, int len2, int start, int maxDistance, int[] char1Costs, int[] prevChar1Costs)
        {

            int i, j;
            for (j= 0; j < maxDistance;) char1Costs[j]= ++j;
            for (; j < len2;) char1Costs[j++]= maxDistance + 1;

            int lenDiff= len2 - len1;
            int jStartOffset= maxDistance - lenDiff;
            int jStart= 0;
            int jEnd= maxDistance;

            char char1= ' ';
            int currentCost= 0;
                int leftCharCost, aboveCharCost;

            for (i= 0; i < len1; ++i)
            {
                char prevChar1= char1;
                char1= string1[start + i];

                char char2= ' ';
                leftCharCost= aboveCharCost= i;
                int nextTransCost= 0;

                // 不需要查看超出右下对角线 - maxDistance 单元格（右下对角线是 i - lenDiff）
                // 和左上对角线 + maxDistance 单元格（左上对角线是 i）
                jStart += (i > jStartOffset) ? 1 : 0;
                jEnd += (jEnd < len2) ? 1 : 0;

                for (j= jStart; j < jEnd; ++j)
                {
                    int thisTransCost= nextTransCost;
                    nextTransCost= prevChar1Costs[j];
                    prevChar1Costs[j]= currentCost= leftCharCost; // 对角线成本（替换）
                    leftCharCost= char1Costs[j];     // 左边现在等于当前成本（下一次迭代时将是对角线）

                    char prevChar2= char2;
                    char2= string2[start + j];

                    if (char1 != char2)
                    {
                        // 如果不满足以下两个条件，则进行替换
                        if (aboveCharCost < currentCost) currentCost= aboveCharCost; // 删除
                        if (leftCharCost < currentCost) currentCost= leftCharCost;   // 插入

                        ++currentCost;

                        if ((i != 0) && (j != 0)
                            && (char1== prevChar2)
                            && (prevChar1== char2)
                            && (thisTransCost + 1 < currentCost))
                        {
                            currentCost= thisTransCost + 1; // 转换
                        }
                    }

                    char1Costs[j]= aboveCharCost= currentCost;
                }

                if (char1Costs[i + lenDiff] > maxDistance) return -1;
            }

            return (currentCost <= maxDistance) ? currentCost : -1;
        }

    }
}
/*
许可声明：
特此授予任何获得本软件及其相关文档文件（以下简称“软件”）副本的人免费使用、复制、修改、合并、发布、分发、转授许可和/或销售软件副本的权利，并允许接收软件的人这样做，但需遵守以下条件：

上述版权声明和许可声明必须包含在软件的所有副本或重要部分中。

软件按“原样”提供，没有任何形式的保证，无论是明示的还是暗示的，包括但不限于适销性、适用于特定目的和不侵权的保证。在任何情况下，作者或版权所有者均不对任何索赔、损害或其他责任负责，无论是在合同、侵权或其他行为中产生的，还是与软件或使用软件或与之相关的其他交易有关的。
*/
